//You are given a nested list of integers nestedList. Each element is either an 
//integer or a list whose elements may also be integers or other lists. Implement 
//an iterator to flatten it. 
//
// Implement the NestedIterator class: 
//
// 
// NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with 
//the nested list nestedList. 
// int next() Returns the next integer in the nested list. 
// boolean hasNext() Returns true if there are still some integers in the nested
// list and false otherwise. 
// 
//
// 
// Example 1: 
//
// 
//Input: nestedList = [[1,1],2,[1,1]]
//Output: [1,1,2,1,1]
//Explanation: By calling next repeatedly until hasNext returns false, the order
// of elements returned by next should be: [1,1,2,1,1].
// 
//
// Example 2: 
//
// 
//Input: nestedList = [1,[4,[6]]]
//Output: [1,4,6]
//Explanation: By calling next repeatedly until hasNext returns false, the order
// of elements returned by next should be: [1,4,6].
// 
//
// 
// Constraints: 
//
// 
// 1 <= nestedList.length <= 500 
// The values of the integers in the nested list is in the range [-106, 106]. 
// 
// Related Topics 栈 设计 
// 👍 328 👎 0


package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;

//Java：Flatten Nested List Iterator
 class P341FlattenNestedListIterator {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        Iterator<Integer> iterator = list.iterator();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    public interface NestedInteger {

        // @return true if this NestedInteger holds a single integer, rather than a nested list.
        public boolean isInteger();

        // @return the single integer that this NestedInteger holds, if it holds a single integer
        // Return null if this NestedInteger holds a nested list
        public Integer getInteger();

        // @return the nested list that this NestedInteger holds, if it holds a nested list
        // Return empty list if this NestedInteger holds a single integer
        public List<NestedInteger> getList();
    }

    public class NestedIterator implements Iterator<Integer> {
        List<Integer> list;
        int cursor;
        int length;

        public NestedIterator(List<NestedInteger> nestedList) {
            list = new ArrayList<>();
            addInteger(nestedList);
            this.cursor = 0;
            this.length = list.size();
        }

        public void addInteger(List<NestedInteger> nestedList) {
            for (NestedInteger nestedInteger : nestedList) {
                if (nestedInteger.isInteger()) {
                    list.add(nestedInteger.getInteger());
                } else {
                    addInteger(nestedInteger.getList());
                }
            }
        }

        @Override
        public Integer next() {
            return list.get(cursor++);

        }

        @Override
        public boolean hasNext() {
            return this.cursor < length ? true : false;
        }
    }

    public class NestedIterator1 implements Iterator<Integer> {

        Stack<NestedInteger> stack;

        public NestedIterator1(List<NestedInteger> nestedList) {
            stack = new Stack<>();
            for (int i = nestedList.size() - 1; i >= 0; i--) {
                stack.push(nestedList.get(i));
            }
        }

        @Override
        public Integer next() {
            NestedInteger peek = stack.peek();
            while (!peek.isInteger()) {
                stack.pop();
                List<NestedInteger> list = peek.getList();
                for (int i = list.size() - 1; i >= 0; i--) {
                    stack.push(list.get(i));
                }
                if (stack.empty()) {
                    break;
                }
                peek = stack.pop();
            }
            NestedInteger pop = stack.pop();
            return pop.getInteger();
        }

        @Override
        public boolean hasNext() {
            return stack.isEmpty() ? false : true;
        }
    }
/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */
//leetcode submit region end(Prohibit modification and deletion)

}